//题目:
// 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
// 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
// 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

// 示例 1：
// 输入：nums = [10,9,2,5,3,7,101,18]
// 输出：4
// 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

// 示例 2：
// 输入：nums = [0,1,0,3,2,3]
// 输出：4

// 示例 3：
// 输入：nums = [7,7,7,7,7,7,7]
// 输出：1

// 提示：
// 1 <= nums.length <= 2500
// -104 <= nums[i] <= 104
 
// 进阶：
// 你能将算法的时间复杂度降低到 O(n log(n)) 吗?
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
//代码
class Solution 
{
    int ret=0;
    int arr[20001]={0};//备忘录
public:
    //计算以pos位置为起始的最长递增子序列
    int dfs(vector<int>& nums,int pos)
    {
        //只要能进这个函数，就说明pos是合法的
        if(arr[pos]!=0) return arr[pos];//记忆功能，可以省去大量的、重读的计算

        int ret=1;//这个1表示nums[pos]自己的长度
        for(int i=pos+1;i<nums.size();i++)
        {
            if(nums[i]>nums[pos])
            {
                ret=max(ret,1+dfs(nums,i));//dfs表示nums[pos]后面符合题意的数组长度
            }
        }

        arr[pos]=ret;//记录以nums[pos]为起始位置的最长递增子序列长度
        return ret;
    }
    int lengthOfLIS(vector<int>& nums) 
    {
        //法一：记忆化搜索
        // int ret=0;
        // for(int i=0;i<nums.size();i++)
        //     ret=max(ret,dfs(nums,i));
        // return ret;

        //法二：动态规划
        //1.创建dp表————dp[i]表示以nums[i]为起点，到数组最后一个元素的“最长递增子序列长度”
        // vector<int> dp(nums.size());
        // //2.初始化
        // dp[nums.size()-1]=1;
        // //3.填表————动态转移方程：dp[i]=nums[i]<nums[i+1]?dp[i+1]+1:就跟nums[i+2]比，直到比到最后一个元素
        // for(int i=nums.size()-2;i>=0;i--)
        // {
        //     dp[i]=1;//nums[i]自己的长度
        //     int max_len=0;
        //     for(int j=i+1;j<nums.size();j++)
        //         if(nums[i]<nums[j])
        //             max_len=max(max_len,dp[j]);//后续最大递增子序列的长度
        //     dp[i]+=max_len;
        // }
        // //4.确定返回值
        // int ret=1;
        // for(int i=0;i<nums.size();i++)
        //     ret=max(ret,dp[i]);
        // return ret;

        //法三：贪心（动规 + 二分）
        vector<int> dp;//记录长度为n的子序列的最后一个元素值

        dp.push_back(nums[0]);

        for(int i=1;i<nums.size();i++)
        {
            //判断将nums[i]插入到dp的哪个位置
            if(nums[i]>dp.back()) dp.push_back(nums[i]);
            else
            {
                int left=0,right=dp.size()-1,mid;
                while(left<=right)
                {
                    mid=(left+right)/2;
                    if(nums[i]>dp[mid]) left=mid+1;
                    if(nums[i]<dp[mid]) right=mid-1;
                    if(nums[i]==dp[mid]) break;
                }
                if(left==right+1)
                    dp[left]=nums[i];
            }
        }

        return dp.size();
    }
};